It is often desirable to model and analyze relationships among objects of interest. A network (or a graph) is one of such modeling representations. There are three elements in a network representation: nodes, links, and paths. The objects of interest are called nodes and the relationships between nodes are called links. A path is an ordered list of links and typically with no repeating nodes or links. Only connectivity information is needed for modeling a network. In addition, the concept of cost (or weight) may be introduced in links and nodes if cost needs to be taken into account during the analysis.
Software products have been developed for performing network analysis. Two popular products are NetEngine™ and the LEDA™ library. NetEngine is primarily used for geographic applications while the LEDA™ library is for general graph/network problems.
NetEngine™ provides a program library designed for geographic network analysis and provides the capability to define, store, traverse, and analyze many kinds of networks through a C application program interface (API) or through a Visual Basic® type library. NetEngine™ is delivered with a set of network analysis algorithms including determining the shortest path between two or more points, solving the traveling salesman problem, identifying the “closest” object meeting a stated criteria, computing origin-destination distance matrices, and allocating service areas to a location. NetEngine™ employs in-memory data structures and methods, and stores each network topology to a permanent disk file. NetEngine™ is available from ESRI, 380 New York Street, Redlands, Calif. (http://www.esri.com).
LEDA™, an acronym for “Library of Efficient Data types and Algorithms,” is implemented by a C++ class library available from Algorithmic Solutions Software GmbH, Saarbrücken, Germany (http://www.algorithmic-solutions.com). The LEDA™ library provides standard graph data types and a wide variety of graph and network algorithms like depth-first search, breadth-first search, shortest paths, minimal spanning trees, matching, weighted matching, network flow, planarity testing, and graph layout.
Available software products present several difficulties. They typically employ proprietary file formats so that network data and the results of network analysis are difficult to exchange, share, and manage. Network information is not separated from applications and requires customized solutions and is accompanied by high maintenance costs. The available data structures and algorithms can incur performance and data management problems when used with the large data sets often present in spatial applications.